<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            因为*会影响前一个字符是否出现，如果从左向右遍历，我们需要考虑后一个字符是否是*,就会很复杂
            而从右向左遍历，就只需要判断最右侧如果匹配，剩余字符是否匹配。只不过最右侧需要分情况讨论是否是*

            ①定义dp数组和下标含义
            dp[i][j]表示长度为i的字符s(0,i-1)与长度为j的字符p(0,j-1)是否匹配
           

            ②定义状态转移方程
            分情况讨论：
                1、如果最右端相同或者最右端是*
                    即s[i-1]==p[j-1]||p[j-1]='*'，那么只需要判断字符s剩余长度i-1 s(0,i-2)与字符p剩余长度j-1 s(0,j-2)是否匹配即dp[i-1][j-1]
                    dp[i][j]=dp[i-1][j-1]
                2、如果最右端不相同，不能直接判死刑，因为p的最右端可能是*
                    2.1 如果p[j-1]!=* 那么直接判死刑
                    2.2 如果p[j-1]==*,(*号可以让前一个字符出现0、1、多次)
                        因此，我们需要比较s[i-1]是否等于p[j-2]或者p[j-2]=='.'

                        2.2.1（当前前提下p[j-1]==*）
                            如果s[i-1]==p[j-2] 即s='aab' p='aabb*'的情况，那么需要干掉一个b，即重复0次
                            那么dp[i][j]就依赖于s(0,i-1)与p(0,j-3)的状态
                            即dp[i][j]=dp[i][j-2]
                        2.2.2
                            如果s[i-1]==p[j-2] 即s='aab' p='aab*',那么重复1次
                            所以只需要判断s(0,i-2)与p(0,j-3)是否匹配
                            dp[i][j]=dp[i-1][j-2]

                        2.2.3如果s[i-1]==p[j-2] 即s='aabbb' p='aab*'的情况，那么需要p重复多次，等价于删除s多次
                            所以只需要判断s(0,i-2)是否与p(0,j-1)匹配,因为可能删除多次，*还需要多次考虑
                            dp[i][j]=dp[i-1][j]

                        如果s[i-1]!=p[j-2],就是让b干掉一次即可，继续比较s(0,i-1)与p(0,j-3)
                        dp[i][j]=dp[i][j-2]

                ③初始化dp数组
                dp[0][0]=true 两个都为空
                当s为空的时候，我们需要判断p[j-1]是否为*，如果为*的话，它可以删除p[j-2]所以我们需要判单s(0,0)是否与p(0,j-3)是否匹配
                dp[0][j]=dp[0][j-2]

                ④确定遍历顺序
                当前状态依赖于前面的状态，所以从左往右

            */
            var isMatch = function (s, p) {
                let dp = new Array(s.length + 1).fill().map(() => new Array(p.length + 1).fill(false))
                dp[0][0] = true
                //初始化状态 如果s为空串且p[j-1]='*',那么只需要判断p(0,j-3)是否匹配，因为p[j-2]可以被删除
                for (let j = 1; j <= p.length; j++) {
                    if (p[j - 1] == '*') {
                        dp[0][j] = dp[0][j - 2]
                    }
                }
                for (let i = 1; i <= s.length; i++) {
                    for (let j = 1; j <= p.length; j++) {
                        if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                            dp[i][j] = dp[i - 1][j - 1]
                        } else if (p[j - 1] == '*') {
                            //先分两种情况 s[i-1]==p[j-2]  s[i-1]!=p[j-2]
                            if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                                //如果相同，有三种情况，满足一种即可
                                dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j]
                            } else {
                                //不同的话，没关系，*可以删除p[j-2] 继续比较s(0,i-1)与p(0,j-3)是否匹配
                                dp[i][j] = dp[i][j - 2]
                            }
                        }
                    }
                }
                return dp[s.length][p.length]
            }
            isMatch('aab', 'aab')
        </script>
    </body>
</html>
